package com.chj.leetcode.tijie200to250;

public class Code213_HouseRobberII {
	public int rob(int[] A) {
		int n = A.length;
		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			return A[0];
		}

		int[] nums = new int[n - 1];
		int res = Integer.MIN_VALUE;
		int i;

		for (i = 0; i < n - 1; i++) {
			nums[i] = A[i];
		}
		res = Math.max(res, calc(nums));

		for (i = 0; i < n - 1; i++) {
			nums[i] = A[i + 1];
		}
		res = Math.max(res, calc(nums));

		return res;

	}

	public int calc(int[] A) {
		int n = A.length;
		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			return A[0];
		}

		int[] dp = new int[n + 1];
		dp[0] = 0;
		dp[1] = A[0];
		for (int i = 2; i <= n; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + A[i - 1]);
		}

		return dp[n];
	}
}
